// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

func topNFreq(array []int, n int) []int {

	bucket := make([][]int, len(array)+1)
	freq := make(map[int]int)

	for _, i := range array {
		v, ok := freq[i]
		if ok {
			freq[i] = v + 1
		} else {
			freq[i] = 1
		}
	}

	for k, v := range freq {
		if bucket[v] == nil {
			bucket[v] = make([]int, 0)
		}
		bucket[v] = append(bucket[v], k)
	}

	res := make([]int, n)
	cnt := 0
	for i := len(bucket) - 1; i >= 0 && cnt < n; i-- {
		if bucket[i] != nil {
			for _, i := range bucket[i] {
				res[cnt] = i
				cnt++
			}
		}
	}
	return res
}

func main() {
	array := []int{1, 6, 6, 8, 8, 8, 3, 3}
	k := 3
	res := topNFreq(array, k)
	fmt.Println(res)
}

//$ go run interview6-16.go
//[8 3 6]
